A common problem in communications networks is the cross-correlation of network flows to identify:                traffic routing issues,        jitter and latency in media,        packet loss and packet re-ordering,        address translation mappings,        correct operation of load balancers, and        loss of privacy in traffic anonymizing mixers.        
A simple environment is shown in FIG. 1 where the two ingress packet flows 100 and 102 are partially mixed on the egress flows 104 and 106 and experience jitter. The term “packet flow” as used herein, refers to a group of related packets, typically having one or more common packet header parameters. In FIG. 1, packet number 2 from ingress flow 102 appears in egress flow 104. Similarly, packet number 2 in ingress flow 100 appears in egress flow 106. Because of different delays experienced by packets as the packets travel through different paths across a network, jitter may result. In FIG. 1, the jitter is illustrated by the difference in inter-arrival times of packets 1 and 3 in egress flow 104 versus packets 1 and 2 in egress flow 106. It is desirable to use methods, such as correlation between network flows, to measure such jitter.
One approach to performing correlation between packet flows is to track a unique identifier included in a packet occurring a known location in a packet flow and timestamp the packet at the ingress and egress points in the network to determine the latency. Such an approach is described in U.S. Pat. No. 6,922,417. The disadvantages of this method are that it only provides a single latency measurement and cannot be practically used for jitter occurring within the flow. To measure jitter using such a method, each packet would have to be timestamped at ingress and egress points, latency would then be calculated for each packet, and then the different latencies could be compared to measure jitter. Time stamping each packet at the ingress and egress points in calculating latency for each packet may be computationally impractical, especially in high speed networks.
Jitter can be accurately measured if timing and sequencing information is included in every packet. One protocol where timing and sequencing information is included in every packet is the real time protocol (RTP), as described in Internet Engineering Task Force (IETF) Request for Comments (RFC) 1889, and used for media streams. According to RFC 1889, synchronized clocks can be used to timestamp monitored packets at the ingress and egress, and latency and jitter can be calculated throughout the stream. Packet drops and retransmissions can also be detected using the sequencing information in the packets. The disadvantages of this method are that large amounts of data must be collected from the network, synchronized clocks must be implemented in the network, and the protocol being measured must explicitly support timestamps and sequence numbers. A variation on this technique is to inject timing packets in-band with the media streams, an example being the precision time protocol (PTP) described in the IEEE 1588 standards. This method eliminates the need to have timestamps in the packets, but is less accurate because timing packets may be treated differently by the network than media packets.
Another approach to measuring packet timings in a packet flow is packet sampling, as described in U.S. Pat. No. 5,315,580. This method greatly reduces data traffic and can identify large scale traffic trends but cannot perform precision measurements, such as jitter, within a flow.
A more brute force approach to measuring differences in packet timings is to perform cross-correlation on traffic flows. An example of such cross-correlation is described in “Network Traffic Behavior Analysis by Decomposition into Control and Data Planes,” IEEE International Symposium on Parallel and Distributed Processing (IPDPS) (2008). This method selects features from packets and then performs a Pearson cross-correlation. This method allows a variety of analysis to be performed but the computational complexity is O(N2), which makes the method difficult to scale. The method also requires mass data collection which may have privacy concerns.
In light of the disadvantages associated with conventional methods for monitoring networks and measuring packet timings, there exists a need for improved methods, systems, and computer readable media for monitoring communications networks. Such methods, systems, and computer readable media preferably provide reduced computational complexity over conventional methods and are suitable for analyzing load volumes of packets.